package com.sheng.leetcode.year2024.month01.day04;

import org.junit.Test;

/**
 * @author by ls
 * @date 2024/1/4
 * <p>
 * 2397. 被列覆盖的最多行数<p>
 * <p>
 * 给你一个下标从 0 开始、大小为 m x n 的二进制矩阵 matrix ；<p>
 * 另给你一个整数 numSelect，表示你必须从 matrix 中选择的 不同 列的数量。<p>
 * 如果一行中所有的 1 都被你选中的列所覆盖，则认为这一行被 覆盖 了。<p>
 * 形式上，假设 s = {c1, c2, ...., cnumSelect} 是你选择的列的集合。
 * 对于矩阵中的某一行 row ，如果满足下述条件，则认为这一行被集合 s 覆盖：<p>
 * 对于满足 matrix[row][col] == 1 的每个单元格 matrix[row][col]（0 <= col <= n - 1），<p>
 * col 均存在于 s 中，或者<p>
 * row 中 不存在 值为 1 的单元格。<p>
 * 你需要从矩阵中选出 numSelect 个列，使集合覆盖的行数最大化。<p>
 * 返回一个整数，表示可以由 numSelect 列构成的集合 覆盖 的 最大行数 。<p>
 * <p>
 * 示例 1：<p>
 * 输入：matrix = [[0,0,0],[1,0,1],[0,1,1],[0,0,1]], numSelect = 2<p>
 * 输出：3<p>
 * 解释：<p>
 * 图示中显示了一种覆盖 3 行的可行办法。<p>
 * 选择 s = {0, 2} 。<p>
 * - 第 0 行被覆盖，因为其中没有出现 1 。<p>
 * - 第 1 行被覆盖，因为值为 1 的两列（即 0 和 2）均存在于 s 中。<p>
 * - 第 2 行未被覆盖，因为 matrix[2][1] == 1 但是 1 未存在于 s 中。<p>
 * - 第 3 行被覆盖，因为 matrix[2][2] == 1 且 2 存在于 s 中。<p>
 * 因此，可以覆盖 3 行。<p>
 * 另外 s = {1, 2} 也可以覆盖 3 行，但可以证明无法覆盖更多行。<p>
 * <p>
 * 示例 2：<p>
 * 输入：matrix = [[1],[0]], numSelect = 1<p>
 * 输出：2<p>
 * 解释：<p>
 * 选择唯一的一列，两行都被覆盖了，因为整个矩阵都被覆盖了。<p>
 * 所以我们返回 2 。<p>
 * <p>
 * 提示：<p>
 * m == matrix.length<p>
 * n == matrix[i].length<p>
 * 1 <= m, n <= 12<p>
 * matrix[i][j] 要么是 0 要么是 1<p>
 * 1 <= numSelect <= n<p>
 */
public class LeetCode2397 {

    @Test
    public void test01() {
//        int[][] matrix = {{0, 0, 0}, {1, 0, 1}, {0, 1, 1}, {0, 0, 1}};
//        int numSelect = 2;
        int[][] matrix = {{1}, {0}};
        int numSelect = 1;
        System.out.println(new Solution().maximumRows(matrix, numSelect));
    }
}

class Solution {

    int[][] matrix;

    int m, n, ans;

    public int maximumRows(int[][] matrix, int numSelect) {
        // 解读：从 0 ~ n 中选取 numSelect 个列，返回能覆盖的列的最大值
        // 覆盖：一行中，所有元素值为 1 的元素，都位于选取的 numSelect 个列上
        this.matrix = matrix;
        m = matrix.length;
        n = matrix[0].length;
        ans = 0;
        dfs(new boolean[n], 0, numSelect);
        // 每行中 1 的个数小于等于 numSelect，才算有效个数
        return ans;
    }

    /**
     * @param flag 代表哪一行是否被选中
     * @param cur  当前位置
     * @param num  剩余选择次数
     */
    public void dfs(boolean[] flag, int cur, int num) {
        if (cur == n && num != 0) {
            return;
        }
        if (num == 0) {
            int max = 0;
            for (int[] ints : matrix) {
                boolean b = true;
                for (int j = 0; j < n; j++) {
                    // 如果当前行为 1，但是没有被选中时
                    if (ints[j] == 1 && !flag[j]) {
                        b = false;
                        break;
                    }
                }
                if (b) {
                    max++;
                }
            }
            ans = Math.max(ans, max);
        } else {
            dfs(flag, cur + 1, num);
            flag[cur] = true;
            dfs(flag, cur + 1, num - 1);
            // 回溯
            flag[cur] = false;
        }
    }
}
